package demo.DataStrucAndAlgo.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Objects;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/4-08-04-16:14
 * @Description：demo.DataStrucAndAlgo.Tree     赫夫曼树（最优二叉树）
 */
/*
赫夫曼树：
    所有叶子结点的带权路径长度之和最小的二叉树，所有叶子结点的带权路径长度又叫WPL。
    WPL=所有叶子结点权值*路径长度之和，
    创建赫夫曼树过程：
        1、将权值数组中的数据包装入事先创建好的结点类中，结点类的num保存权值，然后将每一个结点放入到动态数组（ArrayList）中
        2、将这些动态数组中的结点按照权值大小进行排序
        3、取出权值最小的两个结点，并创建一个新的节点作为这两个节点的父节点，这个父节点的权值为两个子节点的权值之和。
        将这两个节点分别赋给父节点的左右结点。
        4、删除这两个结点，将父节点添加进动态数组里
        5、重复第二步到第四步，直到集合中只剩一个元素，结束循环，最后一个元素就是赫夫曼树的根节点
 */
class Node_heffman implements Comparable<Node_heffman> {
    private int data;
    private Node_heffman left;

    public Node_heffman getLeft() {
        return left;
    }

    public void setLeft(Node_heffman left) {
        this.left = left;
    }

    public Node_heffman getRight() {
        return right;
    }

    public void setRight(Node_heffman right) {
        this.right = right;
    }

    private Node_heffman right;

    public Node_heffman(int data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node_heffman{" +
                "data=" + data +
                '}';
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node_heffman that = (Node_heffman) o;
        return data == that.data;
    }

    @Override
    public int hashCode() {
        return Objects.hash(data);
    }

    @Override
    public int compareTo(Node_heffman o) {
        return this.data - o.data;
    }
}
class huffMan_tree_use{
    private Node_heffman root = null;

    public Node_heffman getRoot() {
        return root;
    }

    public void createTree(ArrayList<Node_heffman>  list ){
        if(list.size()<1){
            throw new RuntimeException("当前集合为空");
        }
        Collections.sort(list);
        System.out.println(list);
        Node_heffman root = list.get(0);   //结点，作为目前的根节点
        while(list.size() > 1){
            Collections.sort(list);

            Node_heffman  node1 = list.remove(0);   //获取第一个叶子结点
            Node_heffman  node2 = list.remove(0);   //获取第二个叶子结点

            root = new Node_heffman(node1.getData() + node2.getData());  //封装新节点
            root.setLeft(node1);
            root.setRight(node2);
            list.add(root);      //将新的权值加入集合进行排序
        }
        this.root = root;
    }

    public void show(Node_heffman node){
        Node_heffman temp = node;
        if(temp.getLeft()!=null){
            show(temp.getLeft());
        }
        if(temp.getRight() == null && temp.getLeft() == null){     //只打印叶子结点
            System.out.println(temp);
        }
        if(temp.getRight()!=null){
            show(temp.getRight());
        }
        //System.out.println(temp);
    }
}
public class HuffmanTree {
    public static void main(String[] args) {
        ArrayList<Node_heffman> list = new ArrayList<>();
        list.add(new Node_heffman(2));
        list.add(new Node_heffman(15));
        list.add(new Node_heffman(8));
        list.add(new Node_heffman(10));
        list.add(new Node_heffman(3));
        list.add(new Node_heffman(1));
        list.add(new Node_heffman(24));

        huffMan_tree_use use = new huffMan_tree_use();
        use.createTree(list);
        use.show(use.getRoot());
    }
}
